package minima

import "math"

func Minima(f func(float64) float64, min, max float64, bits, max_iter int) (float64, float64) {

	var mid, u, fu, fract1, fract2 float64
	tolerance := 1.0 * math.Pow(2, float64(1-bits))

	golden := 0.3819660 // golden ratio, don't need too much precision here!

	x, w, v := max, max, max
	fw, fv, fx := f(x), f(x), f(x)
	delta2, delta := float64(0), float64(0)

	count := max_iter

	for count > 0 {
		mid = (min + max) / 2
		fract1 = tolerance*math.Abs(x) + tolerance/4
		fract2 = 2 * fract1
		if math.Abs(x-mid) <= fract2-(max-min)/2 {
			break
		}
		if math.Abs(delta2) > fract1 {
			r := (x - w) * (fx - fv)
			q := (x - v) * (fx - fw)
			p := (x-v)*q - (x-w)*r
			q = 2 * (q - r)
			if q > 0 {
				p = -p
			}
			q = math.Abs(q)
			td := delta2
			delta2 = delta
			if math.Abs(p) >= math.Abs(q*td/2) || p <= q*(min-x) || p >= q*(max-x) {
				if x >= mid {
					delta2 = min - x
				} else {
					delta2 = max - x
				}
				delta = golden * delta2
			} else {
				delta = p / q
				u = x + delta
				if ((u - min) < fract2) || ((max - u) < fract2) {
					if (mid - x) < 0 {
						delta = -math.Abs(fract1)
					} else {
						delta = math.Abs(fract1)
					}
				}
			}
		} else {
			// golden section:
			if x >= mid {
				delta2 = min - x
			} else {
				delta2 = max - x
			}
			delta = golden * delta2
		}
		// update current position:
		if math.Abs(delta) >= fract1 {
			u = x + delta
		} else if delta > 0 {
			u = x + math.Abs(fract1)
		} else {
			u = x - math.Abs(fract1)
		}
		fu = f(u)
		if fu <= fx {
			// good new point is an improvement!
			// update brackets:
			if u >= x {
				min = x
			} else {
				max = x
			}
			// update control points:
			v = w
			w = x
			x = u
			fv = fw
			fw = fx
			fx = fu
		} else {
			// Oh dear, point u is worse than what we have already,
			// even so it *must* be better than one of our endpoints:
			if u < x {
				min = u
			} else {
				max = u
			}
			if (fu <= fw) || (w == x) {
				// however it is at least second best:
				v = w
				w = u
				fv = fw
				fw = fu
			} else if (fu <= fv) || (v == x) || (v == w) {
				// third best:
				v = u
				fv = fu
			}
		}
		count--
	}
	return x, fx
}
